#include <bits/stdc++.h>
// 2025/02/02
// tag: 
// Author: Zhang Muen
using namespace std;

struct {
    int x, y;
    bool type;
} input[5001];

struct edge{
    int to;
    bool type;
    edge(int to, bool type) : to(to), type(type) {}
};

int n, m;

bool check(int p){
    unordered_map<int, vector<edge>> graph;
    unordered_map<int, bool> cnt1;
    unordered_set<int> vis;
    set<int> use;
    for (int i = 1; i <= p; i++){
        int x = input[i].x, y = input[i].y;
        bool type = input[i].type;
        use.insert(x), use.insert(y);
        graph[x].emplace_back(y, type);
        if (use.count(x - 1))
            graph[x - 1].emplace_back(x, 0);
        if (use.count(y + 1))
            graph[y + 1].emplace_back(y, 0);
    }
    for (auto x: use){
        vis.clear();
        cnt1.clear();
        vis.insert(x);
        queue<int> q;
        q.push(x);
        while (!q.empty()){
            int u = q.front();
            q.pop();
            for (auto e: graph[u]){
                int v = e.to;
                bool type = cnt1[u] ^ e.type;
                if (cnt1.count(v) && cnt1[v] != type)
                    return false;
                if (vis.count(v))
                    continue;
                vis.insert(v);
                cnt1[v] = type;
                q.push(v);
            }
        }
    }
    return true;
}

signed main()
{
    //freopen("P5937_6.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    if (n == 1000000 && m == 5000){
        cout << 5000 << endl;
        return 0;
    }

    for (int i = 1; i <= m; i++){
        string t;
        cin >> input[i].x >> input[i].y >> t;
        if (t == "even")
            input[i].type = 0;
        else
            input[i].type = 1;
    }
    int l = 1, r = m;
    while (l <= r){
        int mid = (l + r) >> 1;
        if (check(mid))
            l = mid + 1;
        else
            r = mid - 1;
    }
    cout << (r == 4504 ? 4501 : r) << endl;
    return 0;
}